In image processing, there are three main types of features that are extracted from images: color, texture, and shape. The focus of this application is on shape-based image feature extraction.
Image feature extraction is widely used in various fields. For example, in the field of image retrieval, a search engine provides pictorial-query services by comparing images in an image database with an image provided by a user, then returning an image from the image database which is most similar to the image given by the user. In such image retrieval systems, features of the images are compared; therefore, it is essential to perform feature extraction operations on those images in advance.
Typically, Hough transformation is used in shape-based image feature extraction and digital image processing. The Hough transformation maps a point in an image plane to a line in a parameter plane and extracts image features according to their statistical characteristics. The main idea of the Hough transformation is as follows: in the image space, a straight line can be represented by the equation y=k*x+b, with k being the slope parameter and b being the intercept parameter. Each straight line passing through the point (x0, y0) has parameters that can be described as y0=k*x0+b. For a point in the target image plane (x, y) that meets a predetermined luminosity condition, a corresponding straight line in the (k, b) parameter plane can be obtained using the equation b=y-k*x. Each point on the straight line is assigned the value of one; and for a point where multiple such straight lines intersect, the point is assigned a value that is the number of the straight lines passing through that point. According to this procedure, a family of straight lines in the target image plane (x, y) can be obtained to represent a straight line in the (k, b) parameter plane. A point where these straight lines intersect in the (k, b) parameter plane has the highest value. Then, this point in the (k, b) parameter plane represents the straight line in the target image plane (x, y). Thus, using the procedure described above, a straight line in the plane can be detected by computing and finding a point having the highest value in the parameter plane. Multiple straight lines can be detected in the same manner. A similar approach can be used for circles and arcs.
As an example, the conventional Hough transformation approach in image feature extraction is further illustrated using FIG. 1. The image in FIG. 1 has the size of 10*10 pixels. Using the bottom left corner of the image as the origin of the ordinate, a straight line in the image can be described by the equation y=5. Suppose that the background of the image has a lower luminosity and points on the straight line have higher luminosities. Using the Hough transformation, the straight line can be detected by the following procedure:
Step 1: detect each point of the image in FIG. 1 according to its coordinates.
Step 2: if a point (x0, y0) in the target image is detected to have a higher luminosity than a predetermined threshold, a straight line b=y0−k*x0 in the parameter plane (as illustrated in FIG. 2) is identified, then a value (i.e., a value) of one is assigned to each point on the straight line identified;
Step 3: for an intersection point of identified straight lines in the parameter plane, defining a value of the intersection point to be the number of straight lines passing through the point. Alternatively, a value of the intersection point may be defined as the sum of a values of the straight lines passing through the point.
As a result, for straight line y=5 in the target image in FIG. 1, a point in the parameter plane of FIG. 2 can be identified which has the highest a value and its parameters k=0 and b=5. Thus, the point (0, 5) in the parameter plane represents the straight line y=5 in the target image. And coordinate values 0 and 5 are the slope parameter and the intercept parameter, respectively. Therefore, the straight line y=5 in the target plane is detected by the point (0, 5) in the parameter plane.
Image feature extraction using the Hough transformation involves computing with floating-point numbers. For example, when compute the slope parameter of a straight line, floating-point computation is used. Even more complex floating-point computation is needed for circles and arcs. As is well known by those skilled in the art, floating-point computation poses greater demands on hardware, such as CPUs. As a result, the performance of the hardware is affected. More effective image feature extraction techniques are therefore needed.